<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0056)http://olympiads.win.tue.nl/ioi/ioi95/contest/wires.html -->
<HTLM><HTML><HEAD><TITLE>IOI'95 Task: Wires and Switches</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY background="IOI'95 Task Wires and Switches.files/backgrnd.gif">
<H1><A href="http://olympiads.win.tue.nl/ioi/ioi95/index.html"><IMG 
alt="[ IOI Home page ]" hspace=5 
src="IOI'95 Task Wires and Switches.files/logo.gif" align=middle border=0></A> 
Task: Wires and Switches</H1>
<CENTER><IMG src="IOI'95 Task Wires and Switches.files/wires.gif" align=bottom> 
<BR>Figure&nbsp;1: Cable with three wires and three switches </CENTER>
<P>In Figure&nbsp;1, a cable with three wires connects side&nbsp;<I>A</I> to 
side&nbsp;<I>B</I>. On side&nbsp;<I>A</I>, the three wires are labeled&nbsp;1, 
2, and&nbsp;3. On side&nbsp;<I>B</I>, wires&nbsp;1 and&nbsp;3 are connected to 
switch&nbsp;3, and wire&nbsp;2 is connected to switch&nbsp;1. 
<P>In general, the cable contains <I>m</I>&nbsp;wires (1&lt;=<I>m</I>&lt;=90), 
labeled&nbsp;1 through&nbsp;<I>m</I> on side&nbsp;<I>A</I>, and there are 
<I>m</I>&nbsp;switches on side&nbsp;<I>B</I>, labeled&nbsp;1 
through&nbsp;<I>m</I>. Each wire is connected to exactly one of the switches. 
Each switch can be connected to zero or more wires. 
<H2>Measurements</H2>Your program has to determine how the wires are connected 
to the switches by doing some measurements. Each switch can be made either 
conducting or non-conducting. Initially all switches are non-conducting. A wire 
can be tested on side&nbsp;<I>A</I> with probe&nbsp;<I>P</I>: Lamp&nbsp;<I>L</I> 
will light up if and only if the sensed wire is connected to a conducting 
switch. 
<P>Your program begins by reading one line with the number&nbsp;<I>m</I> from 
<I>standard input</I>. It then can give three kinds of commands by writing a 
line to \emph{standard output}. Each command starts with a single uppercase 
letter: <TT>T</TT> (Test a wire), <TT>C</TT> (Change a switch), 
and&nbsp;<TT>D</TT> (Done). Command&nbsp;<TT>T</TT> is followed by a wire label, 
<TT>C</TT> by a switch label, and <TT>D</TT> by a list whose <I>i</I>-th element 
is the label of the switch to which wire&nbsp;<I>i</I> is connected. 
<P>After commands <TT>T</TT> and <TT>C</TT>, your program should read one line 
from \emph{standard input}. Command&nbsp;<TT>T</TT> returns <TT>Y</TT> (Yes) 
when the wire's switch is conducting (the lamp lights up), otherwise it 
returns&nbsp;<TT>N</TT> (No). Command&nbsp;<TT>C</TT> returns <TT>Y</TT> if the 
new switch state is conducting, and <TT>N</TT> otherwise. The effect of 
command&nbsp;<TT>C</TT> is to change the state of the switch (if it was 
conducting then it will be non-conducting afterwards and vice versa); the result 
is returned just for feedback. 
<P>Your program may give commands&nbsp;<TT>T</TT> and&nbsp;<TT>C</TT> mixed in 
any order. Finally, it gives command&nbsp;<TT>D</TT> and terminates. Your 
program should give no more than nine hundred (900) commands in total. 
<H2>Example</H2>Figure&nbsp;2 presents an example conversation involving 
8&nbsp;commands relating to Figure&nbsp;1. 
<CENTER><PRE>
____________________________________
| Standard Output | Standard Input |
|_________________|________________|
__________________| 3              |
| C 3             | Y              |
| T 1             | Y              |
| T 2             | N              |
| T 3             | Y              |
| C 3             | N              |
| C 2             | Y              |
| T 2             | N              |
| D 3 1 3         |________________|
|_________________|                 
</PRE>Figure&nbsp;2: Example conversation </CENTER>
<HR>
<A href="mailto:ioi95@win.tue.nl">IOI 95</A> </BODY></HTML>
